package gold.digger;

/**
 * Created by fanzhenyu02 on 2020/6/27.
 * common problem solver template.
 */
public class LC208 {

    class Node {
        public boolean setFlag = false;
        public boolean tailFlag = false;
        public Node[] next;

        public Node() {
            this.setFlag = true;
            this.next = new Node[26];
        }
    }

    class Trie {

        public Node head = new Node();//tail 表示虚拟入口层

        /**
         * Initialize your data structure here.
         */
        public Trie() {
            head.setFlag = true;
        }

        /**
         * Inserts a word into the trie.
         */
        public void insert(String word) {
            Node cur = this.head;
            for (int i = 0; i < word.length(); i++) {
                int chPos = word.charAt(i) - 'a';
                if (cur.next[chPos] == null) {
                    cur.next[chPos] = new Node();
                }
                cur = cur.next[chPos];
            }

            cur.tailFlag = true;
        }

        /**
         * Returns if the word is in the trie.
         */
        public boolean search(String word) {
            Node cur = this.head;
            for (int i = 0; i < word.length(); i++) {
                int chPos = word.charAt(i) - 'a';
                if (cur.next[chPos] == null) {
                    return false;
                }
                cur = cur.next[chPos];
            }

            return cur.tailFlag == true;
        }

        /**
         * Returns if there is any word in the trie that starts with the given prefix.
         */
        public boolean startsWith(String prefix) {
            Node cur = this.head;
            for (int i = 0; i < prefix.length(); i++) {
                int chPos = prefix.charAt(i) - 'a';
                if (cur.next[chPos] == null) {
                    return false;
                }
                cur = cur.next[chPos];
            }

            return true;
        }
    }

    /**
     * Your Trie object will be instantiated and called as such:
     * Trie obj = new Trie();
     * obj.insert(word);
     * boolean param_2 = obj.search(word);
     * boolean param_3 = obj.startsWith(prefix);
     */

    public void run() {
        Trie trie = new Trie();
        trie.insert("apple");
        trie.insert("app");
        System.out.println(trie.startsWith("ap"));

    }


    public static void main(String[] args) {
        LC208 an = new LC208();
        String test = "abbbbacd";
        an.run();
    }
}
